package com.qying.sort;

import java.util.Arrays;

public class MergeSort
{

    public static void main(String[] args) {

        int[] arr = Number.arr;

        for (int i : arr) {
            System.out.print(i + ",");
        }
        System.out.println();

        arr = mergerSort(arr);

        for (int i : arr) {
            System.out.print(i + ",");
        }
    }

    private static int[] mergerSort(int[] arr) {
        if (arr.length < 2) return arr;

        int mid = arr.length/2;

        int[] left = Arrays.copyOfRange(arr,0, mid);
        int[] right = Arrays.copyOfRange(arr,mid, arr.length);

        return merger(mergerSort(left), mergerSort(right));

    }

    private static int[] merger(int[] left, int[] right) {
        int[] result = new int[left.length + right.length];
        for (int i=0,j=0,index = 0;index < result.length; index ++) {
            if (i >= left.length) {
                result[index] = right[j++];
            }else if(j>= right.length) {
                result[index] = left[i++];
            }else if(left[i] > right[j]) {
                result[index] = right[j++];
            }else {
                result[index] = left[i++];
            }
        }

        return result;
    }


}
